class DoublyLink:
    """双向链表，通常用来被其他类继承实现队列等"""

    # ---------------------双向节点---------------------
    class _Node:
        __slots__ = 'element', 'prev', 'next'

        def __init__(self, element, prev, next_):
            self.element = element
            self.prev = prev
            self.next = next_

        def __str__(self):
            msg = str(self.element)
            return msg

    # ---------------------双向链表---------------------
    def __init__(self):
        self.header = self._Node(None, None, None)
        self.trailer = self._Node(None, self.header, None)
        self.header.next = self.trailer
        self.size = 0

    def len(self):
        return self.size

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_between(self, data, prev, next_):
        """在 prev和 next之间插入一个链表"""
        newest = self._Node(data, prev, next_)
        prev.next = newest
        next_.prev = newest
        self.size += 1
        return newest

    def del_node(self, node):
        """删除一个链表并返回值"""
        prev = node.prev
        next_ = node.next
        prev.next = next_
        next_.prev = prev
        data = node.element
        node.prev = node.next = node.element = None
        self.size -= 1
        return data

    def clear(self):
        """清空链表元素"""
        if not self.is_empty():
            current = self.header.next
            while current.next is not None:
                current = current.next
                self.del_node(current.prev)
        self.size = 0

    def find_mid(self):
        """通过链接跳跃，找出中间节点的算法"""
        head = self.header.next
        tail = self.trailer.prev
        while True:
            if head.next == tail or head == tail:
                return head.element
            elif head.next == tail.prev:
                return head.next.element
            elif head.prev == tail:
                return tail.element
            else:
                head = head.next.next
                tail = tail.prev.prev

    def links(self, link):
        """将link链表链接到self后面"""
        if not link.size:
            raise Exception('队列为空')
        first = link.header.next
        last = link.trailer.prev

        first.prev = self.trailer.prev
        last.next = self.trailer

        self.trailer.prev.next = first
        self.trailer.prev = last

        link.trailer.prev = None
        link.header.next = None

        self.size += link.size

    def max(self):
        """返回链表中最大值"""
        current_node = self.header.next
        max_ = current_node.element
        while current_node.element is not None:
            if current_node.element > max_:
                max_ = current_node.element
            current_node = current_node.next
        return max_

    def __str__(self):
        data = ['head']
        current = self.header.next
        for _ in range(self.size):
            data.append(current.element)
            current = current.next
        data.append('tail')
        return str(data)
